package E_2024;
/*
    现有一个机器人，可放置于M×N的网格中任意位置，
    每个网格包含一个非负整数编号，
    当相邻网格的数字编号差值的绝对值小于等于1时，机器人可以在网格间移动
    问题：求机器人可活动的最大范围对应的网格点数目。说明：
    .网格左上角坐标为(0,0),右下角坐标为(m−1,n−1)
    .机器人只能在相邻网格间上下左右移动
输入描述
    第1行输入为M和N，M表示网格的行数N表示网格的列数之后M行表示网格数值，
    每行N个数值（数值大小用k表示），数值间用单个空格分隔，行首行尾无多余空格M、N、k均为整数，且1≤M,N≤150，0≤k≤50
输出描述
    输出1行，包含1个数字，表示最大活动区域的网格点数目行首行尾无多余空格
示例一
    输入
    4 4
    1 2 5 2
    2 4 4 5
    3 5 7 1
    4 6 2 4
    输出
    6
示例二
    输入
    2 3
    1 3 5
    4 1 3
    输出
    1
 */
public class E_200_16 {
    public static void main(String[] args) {
        System.out.println(ans(new int[][]{{1,2,5,2},{2,4,4,5},{3,5,7,1},{4,6,2,4}}));
    }
    public static int ans(int[][] arr){
        int[][] temp = new int[arr.length][arr[0].length];
        int ans = 0;
        int max = arr.length * arr[0].length;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (temp[i][j] == 0){
                    // 以当前 i，j 坐标为起点的可活动范围
                    int tt = tt(arr, temp, i, j, arr[i][j]);
                    max -= tt;
                    ans = Math.max(ans,tt);
                }
                // 剩余数量小于当前最大时直接退出
                if (max < ans) {
                    return ans;
                }
            }
        }
        return ans;
    }
    public static int tt(int[][] arr, int[][] temp, int i, int j, int num){
        int ans = 0;
        if (i < 0 || j < 0 || i >= temp.length || j >= temp[0].length || temp[i][j] == 1 || Math.abs(arr[i][j] - num) > 1)
            return ans;
        // 标记已判断位
        temp[i][j] = 1;
        ans ++;
        ans += tt(arr,temp,i - 1,j, arr[i][j]);
        ans += tt(arr,temp,i + 1,j, arr[i][j]);
        ans += tt(arr,temp,i,j - 1, arr[i][j]);
        ans += tt(arr,temp,i,j + 1, arr[i][j]);
        return ans;
    }
}
